#include "mergeSort.h"
#include <stdlib.h>
#include "logger.h"

//Lpos左侧归并数据的起始地址，Lpos右侧归并数据的起始地址，--得到右侧归并数据的终止地址，RightEnd右侧归并数据的终止地址
static void Merge(ElementType *A, ElementType *TmpArray, int Lpos, int Rpos, int RightEnd)
{
    int LeftEnd = Rpos - 1, TmpPos = Lpos, i = 0, NumEle = RightEnd - Lpos + 1;

    while (Lpos <= LeftEnd && Rpos <= RightEnd)
        if (A[Lpos] < A[Rpos])
            TmpArray[TmpPos++] = A[Lpos++];
        else
            TmpArray[TmpPos++] = A[Rpos++];
    while (Lpos <= LeftEnd)
        TmpArray[TmpPos++] = A[Lpos++];
    while (Rpos <= RightEnd)
        TmpArray[TmpPos++] = A[Rpos++];
    for (i = 0; i < NumEle; i++, RightEnd--)
        A[RightEnd] = TmpArray[RightEnd];
}

static void MSort(ElementType *A, ElementType *TmpArray, int Left, int Right)
{
    int Center;
    if (Left < Right)
    {
        Center = (Left + Right) / 2;
        MSort(A, TmpArray, Left, Center);
        MSort(A, TmpArray, Center + 1, Right);
        Merge(A, TmpArray, Left, Center + 1, Right);
    }
}

void Sort(ElementType *A, int N)
{
    ElementType *TmpArray;
    TmpArray = malloc(N * sizeof(*TmpArray));
    if (!TmpArray)
        FatalError("No space free");
    else
    {
        MSort(A, TmpArray, 0, N - 1);
        free(TmpArray);
    }
}